package com.itheima.mysort;

public class A05_QuickDemo1 {
    public static void main(String[] args) {
        //快速排序
        int[] arr = {7, 4, 2, 13, 1, 3, 12, 10, 5, 8, 9, 6, 11};

        //递归方法
        quickSort(arr, 0, arr.length - 1);

        //输出查看
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }

    private static void quickSort(int[] arr, int i, int j) {

        //记录一下当前范围的开始和结束索引
        int start = i;
        int end = j;

        //递归出口
        if (start > end) {
            return;
        }

        //记录基准数
        int baseNumber = arr[i];

        //
        while (start != end) {
            //end开始找
            while (true) {
                if (end <= start || arr[end] < baseNumber) {
                    //找到了
                    break;
                }
                //没找到，换下一个位置
                end--;
            }
            //start开始找
            while (true) {
                if (end <= start || arr[start] > baseNumber) {
                    //找到了
                    break;
                }
                //没找到，换下一个位置
                start++;
            }
            //运行到这里表示出了循环
            //要不就是找到了，要不就是start和end重叠了，直接交换
            //如果是后面这种情况，直接跳出循环
            int temp = arr[end];
            arr[end] = arr[start];
            arr[start] = temp;
        }
        //到这里start和end已经相遇了，基准数归位，（基准数回到他该在的地方）
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;
        //递归调用
        //左边
        quickSort(arr, i, start - 1);
        //右边
        quickSort(arr, start + 1, j);
    }
}
